<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>一致性哈希算法详解 | 分布式系统核心概念</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <style>
        body {
            font-family: 'Noto Sans SC', 'Noto Serif SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f9fafb;
            color: #111827;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #4f46e5 0%, #7c3aed 50%, #9333ea 100%);
        }
        .code-block {
            background-color: #1e293b;
            border-left: 4px solid #7c3aed;
        }
        .key-concept {
            border-left: 3px solid #7c3aed;
            transition: all 0.3s ease;
        }
        .key-concept:hover {
            background-color: #f5f3ff;
            transform: translateX(4px);
        }
        .mermaid-container {
            background: white;
            border-radius: 0.5rem;
            box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1);
            padding: 1.5rem;
        }
        .nav-pill {
            transition: all 0.2s ease;
        }
        .nav-pill:hover {
            background-color: #e9d5ff;
            transform: translateY(-2px);
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4 sm:px-6 lg:px-8">
        <div class="max-w-4xl mx-auto text-center">
            <h1 class="text-4xl md:text-5xl font-bold mb-6 leading-tight">一致性哈希算法</h1>
            <p class="text-xl md:text-2xl font-light mb-8 max-w-3xl mx-auto">分布式系统中数据分布与负载均衡的优雅解决方案</p>
            <div class="flex justify-center space-x-4">
                <a href="#concept" class="nav-pill bg-white text-purple-600 px-6 py-2 rounded-full font-medium">核心概念</a>
                <a href="#implementation" class="nav-pill bg-purple-800 text-white px-6 py-2 rounded-full font-medium">算法实现</a>
                <a href="#visualization" class="nav-pill bg-white text-purple-600 px-6 py-2 rounded-full font-medium">可视化</a>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <div class="max-w-6xl mx-auto px-4 sm:px-6 lg:px-8 py-12">
        <!-- Introduction -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-question-circle text-purple-600 text-2xl mr-3"></i>
                <h2 class="text-2xl font-bold text-gray-800">问题描述</h2>
            </div>
            <div class="bg-white rounded-xl shadow-sm p-6">
                <p class="text-lg text-gray-700 mb-4">在分布式系统中，如何将数据均匀分布到多台服务器上，并在服务器增减时尽量减少数据迁移？</p>
                <p class="text-gray-600">这是构建可扩展分布式系统面临的关键挑战之一。传统哈希取模方法在节点变化时会导致大量数据迁移，而一致性哈希算法提供了更优雅的解决方案。</p>
            </div>
        </section>

        <!-- Key Concepts -->
        <section id="concept" class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-lightbulb text-purple-600 text-2xl mr-3"></i>
                <h2 class="text-2xl font-bold text-gray-800">核心概念与解题思路</h2>
            </div>
            
            <div class="grid md:grid-cols-2 gap-6">
                <!-- Concept 1 -->
                <div class="key-concept bg-white p-6 rounded-lg shadow-sm">
                    <h3 class="text-xl font-semibold text-purple-700 mb-3 flex items-center">
                        <i class="fas fa-circle-nodes mr-2"></i> 哈希环结构
                    </h3>
                    <p class="text-gray-700">将节点和键映射到一个虚拟的哈希环上，键被分配到顺时针方向的第一个节点。这种环形结构使得节点增减时只影响相邻区域的数据。</p>
                </div>
                
                <!-- Concept 2 -->
                <div class="key-concept bg-white p-6 rounded-lg shadow-sm">
                    <h3 class="text-xl font-semibold text-purple-700 mb-3 flex items-center">
                        <i class="fas fa-copy mr-2"></i> 虚拟节点
                    </h3>
                    <p class="text-gray-700">通过为每个物理节点创建多个虚拟节点，可以更均匀地分布负载，避免数据倾斜问题，提高系统的整体平衡性。</p>
                </div>
                
                <!-- Concept 3 -->
                <div class="key-concept bg-white p-6 rounded-lg shadow-sm">
                    <h3 class="text-xl font-semibold text-purple-700 mb-3 flex items-center">
                        <i class="fas fa-clock mr-2"></i> 高效查找
                    </h3>
                    <p class="text-gray-700">使用有序数据结构（如TreeMap）存储节点，可以在O(log n)时间内找到负责特定键的节点，确保高效的数据访问。</p>
                </div>
                
                <!-- Concept 4 -->
                <div class="key-concept bg-white p-6 rounded-lg shadow-sm">
                    <h3 class="text-xl font-semibold text-purple-700 mb-3 flex items-center">
                        <i class="fas fa-arrows-left-right mr-2"></i> 最小数据迁移
                    </h3>
                    <p class="text-gray-700">节点增减时，只有相邻区域的数据需要重新分配，显著减少了传统哈希取模方法导致的大规模数据迁移。</p>
                </div>
            </div>
        </section>

        <!-- Algorithm Complexity -->
        <section class="mb-16 bg-white rounded-xl shadow-sm p-6">
            <h2 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-chart-line text-purple-600 mr-3"></i> 算法复杂度分析
            </h2>
            
            <div class="grid md:grid-cols-2 gap-8">
                <div>
                    <h3 class="text-xl font-semibold text-gray-700 mb-4 border-b pb-2">时间复杂度</h3>
                    <ul class="space-y-3">
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-2"></i>
                            <span><span class="font-medium">节点查找：</span>O(log n) - 使用有序数据结构实现高效查找</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-2"></i>
                            <span><span class="font-medium">节点添加：</span>O(k log n) - k为虚拟节点数量</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-2"></i>
                            <span><span class="font-medium">节点移除：</span>O(k log n) - k为虚拟节点数量</span>
                        </li>
                    </ul>
                </div>
                
                <div>
                    <h3 class="text-xl font-semibold text-gray-700 mb-4 border-b pb-2">空间复杂度</h3>
                    <ul class="space-y-3">
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-2"></i>
                            <span><span class="font-medium">存储需求：</span>O(n) - n为虚拟节点总数</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-2"></i>
                            <span><span class="font-medium">内存使用：</span>与虚拟节点数量成正比</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-2"></i>
                            <span><span class="font-medium">平衡性：</span>虚拟节点越多，内存消耗越大但分布越均匀</span>
                        </li>
                    </ul>
                </div>
            </div>
        </section>

        <!-- Visualization -->
        <section id="visualization" class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-project-diagram text-purple-600 text-2xl mr-3"></i>
                <h2 class="text-2xl font-bold text-gray-800">一致性哈希可视化</h2>
            </div>
            
            <div class="mermaid-container">
                <div class="mermaid">
                    graph LR
                    subgraph 哈希环
                        direction LR
                        N0((0)) --> N1((72))
                        N1 --> N2((144))
                        N2 --> N3((216))
                        N3 --> N4((288))
                        N4 --> N0
                    end
                    
                    subgraph 物理节点
                        S1[服务器A] -->|虚拟节点| N1
                        S1 -->|虚拟节点| N3
                        S2[服务器B] -->|虚拟节点| N2
                        S3[服务器C] -->|虚拟节点| N0
                        S3 -->|虚拟节点| N4
                    end
                    
                    K1[键"用户1"] --> N1
                    K2[键"用户2"] --> N2
                    K3[键"用户3"] --> N3
                    K4[键"用户4"] --> N4
                </div>
            </div>
            
            <div class="mt-6 bg-white p-6 rounded-lg shadow-sm">
                <h3 class="text-xl font-semibold text-purple-700 mb-3">可视化说明</h3>
                <ul class="list-disc pl-5 space-y-2 text-gray-700">
                    <li>哈希环上的每个点代表一个哈希值位置</li>
                    <li>物理节点通过多个虚拟节点分布在环上</li>
                    <li>键被分配到顺时针方向最近的虚拟节点</li>
                    <li>节点增减时，只有相邻区域的数据需要迁移</li>
                </ul>
            </div>
        </section>

        <!-- Implementation -->
        <section id="implementation" class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-code text-purple-600 text-2xl mr-3"></i>
                <h2 class="text-2xl font-bold text-gray-800">Java实现</h2>
            </div>
            
            <div class="code-block rounded-lg overflow-hidden mb-6">
                <div class="flex items-center bg-gray-800 px-4 py-2">
                    <div class="flex space-x-2 mr-4">
                        <span class="w-3 h-3 rounded-full bg-red-500"></span>
                        <span class="w-3 h-3 rounded-full bg-yellow-500"></span>
                        <span class="w-3 h-3 rounded-full bg-green-500"></span>
                    </div>
                    <span class="text-gray-300 text-sm">ConsistentHashing.java</span>
                </div>
                <pre class="text-gray-200 p-4 overflow-x-auto"><code>
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * 一致性哈希算法实现
 * 用于分布式系统中数据的均匀分布和减少节点变化时的数据迁移
 */
public class ConsistentHashing {
    // 虚拟节点的复制因子，越大分布越均匀
    private final int numberOfReplicas;
    // 存储虚拟节点的哈希值到实际节点的映射
    private final SortedMap&lt;Integer, String&gt; circle = new TreeMap&lt;&gt;();
    // 存储实际节点到其虚拟节点哈希值的映射
    private final Map&lt;String, Collection&lt;Integer&gt;&gt; nodeToHashes = new HashMap&lt;&gt;();
    
    /**
     * 构造函数
     * @param numberOfReplicas 每个节点的虚拟节点数量
     */
    public ConsistentHashing(int numberOfReplicas) {
        this.numberOfReplicas = numberOfReplicas;
    }
    
    /**
     * 添加节点到哈希环
     * @param node 节点名称
     */
    public void addNode(String node) {
        Collection&lt;Integer&gt; hashes = new java.util.ArrayList&lt;&gt;();
        
        // 为每个节点创建多个虚拟节点
        for (int i = 0; i &lt; numberOfReplicas; i++) {
            // 计算虚拟节点的哈希值
            int hash = getHash(node + ":" + i);
            // 将虚拟节点添加到哈希环
            circle.put(hash, node);
            // 记录节点对应的哈希值
            hashes.add(hash);
        }
        
        // 保存节点到哈希值的映射，用于节点移除
        nodeToHashes.put(node, hashes);
    }
    
    /**
     * 从哈希环中移除节点
     * @param node 节点名称
     */
    public void removeNode(String node) {
        // 获取节点对应的所有哈希值
        Collection&lt;Integer&gt; hashes = nodeToHashes.get(node);
        if (hashes != null) {
            // 从哈希环中移除所有虚拟节点
            for (int hash : hashes) {
                circle.remove(hash);
            }
            // 从映射中移除节点
            nodeToHashes.remove(node);
        }
    }
    
    /**
     * 根据键获取对应的节点
     * @param key 键
     * @return 负责处理该键的节点，如果环为空则返回null
     */
    public String getNode(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        
        // 计算键的哈希值
        int hash = getHash(key);
        
        // 如果哈希环中没有大于等于该哈希值的节点，则返回环的第一个节点
        if (!circle.containsKey(hash)) {
            // 获取大于等于hash的子映射，如果为空则取整个环的第一个节点
            SortedMap&lt;Integer, String&gt; tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        
        // 返回负责处理该键的节点
        return circle.get(hash);
    }
    
    /**
     * 计算字符串的哈希值
     * @param key 输入字符串
     * @return 哈希值
     */
    private int getHash(String key) {
        // 使用FNV-1a哈希算法
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i &lt; key.length(); i++) {
            hash = (hash ^ key.charAt(i)) * p;
        }
        hash += hash &lt;&lt; 13;
        hash ^= hash &gt;&gt; 7;
        hash += hash &lt;&lt; 3;
        hash ^= hash &gt;&gt; 17;
        hash += hash &lt;&lt; 5;
        
        // 确保哈希值为正数
        return Math.abs(hash);
    }
    
    /**
     * 获取哈希环的大小（虚拟节点数量）
     * @return 哈希环大小
     */
    public int getSize() {
        return circle.size();
    }
    
    /**
     * 使用示例
     */
    public static void main(String[] args) {
        // 创建一致性哈希实例，每个节点有3个虚拟节点
        ConsistentHashing ch = new ConsistentHashing(3);
        
        // 添加三个服务器节点
        ch.addNode("服务器A");
        ch.addNode("服务器B");
        ch.addNode("服务器C");
        
        // 测试一些键的分布
        System.out.println("键'用户1'被分配到: " + ch.getNode("用户1"));
        System.out.println("键'用户2'被分配到: " + ch.getNode("用户2"));
        System.out.println("键'用户3'被分配到: " + ch.getNode("用户3"));
        
        // 移除一个节点
        ch.removeNode("服务器B");
        System.out.println("\n移除'服务器B'后:");
        
        // 查看键的重新分布
        System.out.println("键'用户1'被分配到: " + ch.getNode("用户1"));
        System.out.println("键'用户2'被分配到: " + ch.getNode("用户2"));
        System.out.println("键'用户3'被分配到: " + ch.getNode("用户3"));
    }
}
                </code></pre>
            </div>
            
            <div class="grid md:grid-cols-2 gap-6 mt-8">
                <div class="bg-white p-6 rounded-lg shadow-sm">
                    <h3 class="text-xl font-semibold text-purple-700 mb-3 flex items-center">
                        <i class="fas fa-cogs mr-2"></i> 关键组件
                    </h3>
                    <ul class="list-disc pl-5 space-y-2 text-gray-700">
                        <li><span class="font-medium">哈希环：</span>使用TreeMap实现，支持高效的范围查询</li>
                        <li><span class="font-medium">虚拟节点：</span>通过节点名称+序号创建多个副本</li>
                        <li><span class="font-medium">哈希函数：</span>采用FNV-1a算法确保均匀分布</li>
                        <li><span class="font-medium">反向映射：</span>维护节点到虚拟节点的映射以便快速移除</li>
                    </ul>
                </div>
                
                <div class="bg-white p-6 rounded-lg shadow-sm">
                    <h3 class="text-xl font-semibold text-purple-700 mb-3 flex items-center">
                        <i class="fas fa-play-circle mr-2"></i> 使用示例
                    </h3>
                    <ul class="list-disc pl-5 space-y-2 text-gray-700">
                        <li>初始化时指定每个节点的虚拟副本数</li>
                        <li>添加节点时会自动创建虚拟节点</li>
                        <li>移除节点时会清理所有相关虚拟节点</li>
                        <li>查找操作自动处理环的循环特性</li>
                    </ul>
                </div>
            </div>
        </section>

        <!-- Applications -->
        <section class="bg-white rounded-xl shadow-sm p-6 mb-16">
            <h2 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-rocket text-purple-600 mr-3"></i> 实际应用场景
            </h2>
            
            <div class="grid md:grid-cols-3 gap-6">
                <div class="border-l-4 border-purple-500 pl-4">
                    <h3 class="text-xl font-semibold text-gray-700 mb-2">分布式缓存</h3>
                    <p class="text-gray-600">如Redis集群使用一致性哈希来决定键的分布，确保缓存服务器增减时最小化数据迁移。</p>
                </div>
                
                <div class="border-l-4 border-purple-500 pl-4">
                    <h3 class="text-xl font-semibold text-gray-700 mb-2">负载均衡</h3>
                    <p class="text-gray-600">在反向代理服务器如Nginx中，用于将请求均匀分配到后端服务器。</p>
                </div>
                
                <div class="border-l-4 border-purple-500 pl-4">
                    <h3 class="text-xl font-semibold text-gray-700 mb-2">分布式存储</h3>
                    <p class="text-gray-600">如Amazon Dynamo、Cassandra等系统使用变种实现数据分区。</p>
                </div>
            </div>
        </section>
    </div>

    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>